Breadth-first Search for a Graph

Breadth-first search allows you to find the shortest
distance between two things
BFS takes O(V+E), (V for number of vertices, E for number of edges)

from collections import deque

def person_is_seller(name):
    return name[-1] == "m"

def bfs(gr, init_name):

    search_queue = deque()
    search_queue += gr[init_name]           # = deque(['alice', 'bob', 'claire'])
    # This array is how you keep track of
    # which people you’ve searched before
    searched = []

    while search_queue:
        person = search_queue.popleft()     # performance!!! = 'alice'
        # Only search this person if you
        # haven’t already searched them
        if not person in searched:
            if person_is_seller(person):
                print(person + " is a seller!")
                return True
            else:
                search_queue += gr[person]  # = deque(['bob', 'claire', 'peggy'])
                # Marks this person as searched
                searched.append(person)
    return False

Test

Graph
anuj <-- bob <---- you --> clarie --> thom
          |         |         |
          v         v         v
        peggy <-- alice    jonny

graph = {}
graph["you"]    = ["alice", "bob", "claire"]
graph["bob"]    = ["anuj", "peggy"]
graph["alice"]  = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"]   = []
graph["peggy"]  = []
graph["thom"]   = []
graph["jonny"]  = []

print(bfs(graph, "you"))                    # True => the path is exist
# thom is a seller!